package cn.xiaolang.function.data_structure;

/**
 * 至少是其他数字两倍的最大数
 * <p>
 * 在一个给定的数组nums中，总是存在一个最大元素 。
 * 查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
 * 如果是，则返回最大元素的索引，否则返回-1。
 * </p>
 *
 * @author fuhw/Dean
 * @date 2020-03-26
 */
public class ArrayDominantIndex {

    public static void main(String[] args) {
        // 0 1,0 0,0,3,2  0,0,2,3
        int[] nums = {0};
        System.out.println(dominantIndex(nums));
        System.out.println(dominantIndex2(nums));
    }

    /**
     * 思路：
     * 1 取出最大元素索引
     * 2 遍历元素2倍跟最大元素比较
     * O(2n)复杂度
     *
     * @param nums 指定数组
     * @return 返回数组的中心索引
     */
    public static int dominantIndex(int[] nums) {
        int maxEleIndex = 0;
        // O(n)
        for (int i = 0; i < nums.length; i++) {
            if (nums[maxEleIndex] < nums[i]) {
                maxEleIndex = i;
            }
        }
        // O(n)
        for (int i = 0; i < nums.length; i++) {
            if (maxEleIndex != i && nums[maxEleIndex] < 2 * nums[i]) {
                return -1;
            }

        }
        return maxEleIndex;
    }

    /**
     * 思路：
     * 取出最大元素,第二大元素
     * O(n)复杂度
     *
     * @param nums 指定数组
     * @return 返回数组的中心索引
     */
    public static int dominantIndex2(int[] nums) {
        int maxEleIndex = 0;
        int tow = 0;
        int one = 0;
        // O(n)
        for (int i = 0; i < nums.length; i++) {
            int oldOne = one;
            // 取最大元素
            if (nums[i] > one) {
                one = nums[i];
                maxEleIndex = i;
            }
            // 取第二大元素
            if (tow < nums[i]) {
                tow = oldOne > nums[i] ? nums[i] : oldOne;
            }
        }

        return one >= 2 * tow ? maxEleIndex : -1;
    }
}
